package buildTree

import "fmt"

/**
从前序与中序遍历序列构造二叉树
不会做，多看看题解
*/
type TreeNode struct {
	val   int
	left  *TreeNode
	right *TreeNode
}

var m map[int]int

/*
	pre := []int {3,9,20,15,7}
	in :=  []int {9,3,15,20,7}
*/
func buildTree(preorder []int, inorder []int) *TreeNode {
	m = make(map[int]int, len(inorder))

	for index, v := range inorder {
		m[v] = index
		fmt.Println(m[v])
	}
	return build(0, len(preorder)-1, 0, len(inorder)-1, preorder)
}

func build(pStart, pEnd, inStart, inEnd int, preorder []int) *TreeNode {
	if pStart > pEnd || inStart > inEnd {
		return nil
	}
	node := &TreeNode{val: preorder[pStart]}
	numLeft := m[preorder[pStart]]
	node.left = build(pStart+1, pStart+numLeft-inStart, inStart, numLeft-1, preorder)
	node.right = build(pStart-inStart+numLeft+1, pEnd, numLeft+1, inEnd, preorder)
	return node

}
